#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

char lookahead;
int num;
enum TERMINAL {
    ID,
	ADD,
	MUL,
	LBR,
	RBR,
	END,
	ERR
};

enum NON_TERMINAL {
	E,
	T,
	F
};

enum ACTION_TYPE {
	SHIFT,
	REDUCE,
	ERROR,
	ACC
};

#define NUM_TERMINAL  6
#define NUM_NONTERMINAL  3
#define NUM_STATES  12

struct action{
	enum ACTION_TYPE type;
	int id;
}  actionTable[NUM_STATES][NUM_TERMINAL];

int gotoTable[NUM_STATES][NUM_NONTERMINAL];

int stackPtr;
int stack[1024];
int value[1024];
void push(int state) {
	stack[stackPtr] = state;
	stackPtr ++;
}

void pop() {
	stackPtr --;
}

int top() {
	return stack[stackPtr - 1];
}

void valset(int offset, int v) {
	value[stackPtr - 1 + offset] = v;
}
int valget(int offset) {
	return value[stackPtr - 1 + offset];
}

void init() {
	int i, j;

	//stack
	stackPtr = 0;
	push(0);

	//action and goto tables
	for(i = 0; i < NUM_STATES; i ++) {
		for(j = 0; j < NUM_TERMINAL; j ++) {
		actionTable[i][j].type = ERROR;
		}
		for(j = 0; j < NUM_NONTERMINAL; j ++) {
		gotoTable[i][j] = -1;
		}
	}

	//fill in the goto table
	gotoTable[0][E] = 1;
	gotoTable[0][T] = 2;
	gotoTable[0][F] = 3;
	gotoTable[4][E] = 8;
	gotoTable[4][T] = 2;
    gotoTable[4][F] = 3;
    gotoTable[6][T] = 9;
    gotoTable[6][F] = 3;
    gotoTable[7][F] = 10;
    //fill in the action table
    actionTable[0][ID].type =SHIFT;
	actionTable[0][ID].id = 5;
	actionTable[0][LBR].type = SHIFT;
	actionTable[0][LBR].id = 4;
	actionTable[1][ADD].type = SHIFT;
	actionTable[1][ADD].id =6;
	actionTable[1][END].type= ACC;
	actionTable[2][ADD].type = REDUCE;
	actionTable[2][ADD].id = 2;
	actionTable[2][MUL].type = SHIFT;
	actionTable[2][MUL].id = 7;
	actionTable[2][RBR].type = REDUCE;
	actionTable[2][RBR].id = 2;
	actionTable[2][END].type = REDUCE;
	actionTable[2][END].id = 2;
	actionTable[3][ADD].type=REDUCE;
	actionTable[3][ADD].id=4;
	actionTable[3][MUL].type=REDUCE;
	actionTable[3][MUL].id=4;
	actionTable[3][RBR].type=REDUCE;
	actionTable[3][RBR].id=4;
	actionTable[3][END].type=REDUCE;
	actionTable[3][END].id=4;
	actionTable[4][ID].type=SHIFT;
	actionTable[4][ID].id=5;
	actionTable[4][LBR].type=SHIFT;
	actionTable[4][LBR].id=4;
	actionTable[5][ADD].type=REDUCE;
	actionTable[5][ADD].id=6;
	actionTable[5][MUL].type=REDUCE;
	actionTable[5][MUL].id=6;
	actionTable[5][RBR].type=REDUCE;
	actionTable[5][RBR].id=6;
	actionTable[5][END].type=REDUCE;
	actionTable[5][END].id=6;
	actionTable[6][ID].type=SHIFT;
	actionTable[6][ID].id=5;
	actionTable[6][LBR].type=SHIFT;
	actionTable[6][LBR].id=4;
	actionTable[7][ID].type=SHIFT;
	actionTable[7][ID].id=5;
	actionTable[7][LBR].type=SHIFT;
	actionTable[7][LBR].id=4;
	actionTable[8][ADD].type=SHIFT;
	actionTable[8][ADD].id=6;
	actionTable[8][RBR].type=SHIFT;
	actionTable[8][RBR].id=11;
	actionTable[9][ADD].type=REDUCE;
	actionTable[9][ADD].id=1;
	actionTable[9][MUL].type=SHIFT;
	actionTable[9][MUL].id=7;
	actionTable[9][RBR].type=REDUCE;
	actionTable[9][RBR].id=1;
	actionTable[9][END].type=REDUCE;
	actionTable[9][END].id=1;
	actionTable[10][ADD].type=REDUCE;
	actionTable[10][ADD].id=3;
	actionTable[10][MUL].type=REDUCE;
	actionTable[10][MUL].id=3;
	actionTable[10][RBR].type=REDUCE;
	actionTable[10][RBR].id=3;
	actionTable[10][END].type=REDUCE;
	actionTable[10][END].id=3;
	actionTable[11][ADD].type=REDUCE;
	actionTable[11][ADD].id=5;
	actionTable[11][MUL].type=REDUCE;
	actionTable[11][MUL].id=5;
	actionTable[11][RBR].type=REDUCE;
	actionTable[11][RBR].id=5;
	actionTable[11][END].type=REDUCE;
	actionTable[11][END].id=5;
}

enum TERMINAL lexical(FILE *fp) {

	lookahead = getc(fp);

	while(lookahead == ' ' || lookahead == '\t' || lookahead == '\n') {
		lookahead = getc(fp);
	}

	if(isdigit(lookahead)) {
		num = 0;
		do {
			num = num * 10 + lookahead - '0';
			lookahead = getc(fp);
		} while(isdigit(lookahead));
		ungetc(lookahead, fp);
		return ID;
	} else if (lookahead == '+') {
		return ADD;
	} else if (lookahead == '*') {
		return MUL;
	} else if(lookahead == EOF) {
		return END;
	}else if(lookahead == '(') {
		return LBR;
	} else if(lookahead == ')') {
		return RBR;
	} else {
		return ERR;
	}
}

void parse(enum TERMINAL *input, int *number) {
	int currentState = 0;
	int currentValue = 0;
	int index = 0;
	while(1) {
		printf("currentState: %d\n", currentState);
		switch(actionTable[currentState][input[index]].type) {

			case SHIFT:
				{
                currentValue = number[index];//store the current shifted value for further use
				//how to shift
				valset(0,currentValue);
				currentState=actionTable[currentState][input[index]].id;
				push(currentState);
				index++;
				break;}
			case REDUCE:
				switch(actionTable[currentState][input[index]].id) {
					case 1:
						//reduce by production 1
						{
						    currentValue=valget(-1)+valget(-3);
						    pop();
						    pop();
						    pop();
						    valset(0,currentValue);
						    currentState=gotoTable[stack[stackPtr-1]][E];
						    push(currentState);
						break;
						}
					case 2:
					    {
					        pop();
					         currentState=gotoTable[stack[stackPtr-1]][E];
					         push(currentState);
                             break;
					    }
						//reduce by production 2
					case 3:
						{
						    currentValue=valget(-1)*valget(-3);
                            pop();
						    pop();
						    pop();
                            valset(0,currentValue);
                            //reduce by production 3
						    currentState=gotoTable[stack[stackPtr-1]][T];
						    push(currentState);
						break;
						}
					case 4:
					    {
					        pop();
					        currentState=gotoTable[stack[stackPtr-1]][T];
					        push(currentState);
						//reduce by production 4
						break;}
					case 5:
					    {
					        currentValue=valget(-2);
					        pop();
						    pop();
						    pop();
						    valset(0,currentValue);
					       currentState=gotoTable[stack[stackPtr-1]][F];
					       push(currentState);
						//reduce by production 5
						break;}
					case 6:

					    {
					        pop();
					        currentValue = number[index];
					    currentState=gotoTable[stack[stackPtr-1]][F];
					    push(currentState);
						//reduce by production 6
						break;}
					default:
						printf("ERROR REDUCE\n");
						exit(-1);
						break;
				}
				break;
			case ERROR:
				printf("ERROR ACTION\n");
				exit(-1);
				break;
			case ACC:
				if(input[index] == END) {
					printf("ACC\n");
					return;
				} else {
					printf("ERROR ACC\n");
					exit(-1);
				}
				break;
		}
	}
}


int main(int argc, char **argv) {
	enum TERMINAL input[1024];
	int number[1024];
	int inputIndex = 0;
	FILE *fp;
	enum TERMINAL temp;
	if(argc < 2) {
		printf("insufficient arguments");
		return 1;
	}
	fp = fopen(argv[1], "r");
	while((temp = lexical(fp)) != END) {
		input[inputIndex] = temp;
		number[inputIndex] = (temp == ID ? num : -1);
		inputIndex ++;
	}

	input[inputIndex] = END;
	fclose(fp);

	init();
	parse(input, number);
    printf("%d\n",valget(-1));
	return 0;
}
